class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        def func(word1, i, word2, j, memo):
            if i == len(word1):
                return len(word2) - j
            if j == len(word2):
                return len(word1) - i
            if (i, j) in memo:
                return memo[(i, j)]
            res = 0
            if word1[i] == word2[j]:
                res = func(word1, i + 1, word2, j + 1, memo)
            else:
                replace_cnt = func(word1, i + 1, word2, j + 1, memo)
                insert_cnt = func(word1, i, word2, j + 1, memo)
                remove_cnt = func(word1, i + 1, word2, j, memo)
                res = min(replace_cnt, insert_cnt, remove_cnt) + 1

            memo[(i, j)] = res
            return res

        return func(word1, 0, word2, 0, {})
